#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <assert.h>

/*
	用递归方式实现快速排序。
*/

void swap(int *a, int *b)
{
	int temp = *a;
	*a = *b;
	*b = temp;
}

int median(int array[], int left, int right)
{
	int mid = (left + right) / 2;
	if (array[left] > array[mid])
	{
		swap(&array[left], &array[mid]);
	}
	if (array[mid] > array[right])
	{
		swap(&array[mid], &array[right]);
	}
	if (array[left] > array[mid])
	{
		swap(&array[left], &array[mid]);
	}
	swap(&array[mid], &array[right - 1]);
	return array[right - 1];
}

void quicksort(int array[], int left, int right)
{
	if (left >= right)
	{
		return;
	}
	int pivot = median(array, left, right);
	int i = left, j = right;
	while (1)
	{
		while (array[i] < pivot && i < j)
			i++;
		while (array[j] >= pivot && i < j)
			j--;
		if (i < j)
		{
			swap(&array[i], &array[j]);
		}
		else
		{
			break;
		}
	}
	swap(&array[i], &array[right - 1]);
	quicksort(array, left, i - 1);
	quicksort(array, i + 1, right);
}

void QuickSort(int array[], int n)
{
	quicksort(array, 0, n - 1);
}

int main()
{
	int array[1000];
	int i;
	for (i = 0; i < 1000; i++)
	{
		array[i] = rand() % 10000;
	}
	QuickSort(array, 1000);
	int tag = 0;
	for (int i = 0; i < 999; i++)
	{
		if (array[i] > array[i + 1])
		{
			tag = -1;
			break;
		}
	}
	printf("tag=%d\n", tag);
	return 0;
}
